package com.leetcode.algorithm.y19.m03;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

import com.leetcode.algorithm.common.TreeNode;

/**
 * leetcode-cn.com
 * (done)129. 求根到叶子节点数字之和
 * @author: jie.deng
 * @time: 2019年3月12日 上午12:51:19
 */
public class MySolution0312 {
	
	/**
	 * 129. 求根到叶子节点数字之和
	 * 
	 * 给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
	 * 
	 * 例如，从根到叶子节点路径 1->2->3 代表数字 123。
	 * 
	 * 计算从根到叶子节点生成的所有数字之和。
	 * 
	 * 说明: 叶子节点是指没有子节点的节点。
	 * 
	 * 示例 1:
	 * 
	 * 输入: [1,2,3]
	 *     1
	 *    / \
	 *   2   3
	 * 输出: 25
	 * 解释:
	 * 从根到叶子节点路径 1->2 代表数字 12.
	 * 从根到叶子节点路径 1->3 代表数字 13.
	 * 因此，数字总和 = 12 + 13 = 25.
	 * 示例 2:
	 * 
	 * 输入: [4,9,0,5,1]
	 *     4
	 *    / \
	 *   9   0
	 *  / \
	 * 5   1
	 * 输出: 1026
	 * 解释:
	 * 从根到叶子节点路径 4->9->5 代表数字 495.
	 * 从根到叶子节点路径 4->9->1 代表数字 491.
	 * 从根到叶子节点路径 4->0 代表数字 40.
	 * 因此，数字总和 = 495 + 491 + 40 = 1026.
	 * @param root
	 * @return
	 */
	public int sumNumbers(TreeNode root) {
		int sum = 0;
		if (root == null) {
			return 0;
		}
		Stack<TreeNode> stack = new Stack<TreeNode>();
		StringBuilder path = new StringBuilder();
		Map<TreeNode, String> rightNodePathPrefixMap = new HashMap<TreeNode, String>();
		stack.push(root);
		while (!stack.isEmpty()) {
			TreeNode node = stack.pop();
			if (rightNodePathPrefixMap.containsKey(node)) {
				path = new StringBuilder(rightNodePathPrefixMap.get(node));
			}
			path.append("" + node.val);
			if (node.right != null) { // 右子树先入栈，左子树后入栈，这样出栈就是先左节点后右节点
				stack.push(node.right);
				rightNodePathPrefixMap.put(node.right, path.toString());
			}
			if (node.left != null) {
				stack.push(node.left);
			}
			if (node.left == null && node.right == null) { // 叶子结点
				sum += Integer.parseInt(path.toString());
			}
		}
		return sum;
	}
    
    
}
